#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点的字符数据类型
typedef char ElemType;

// 二叉树节点结构体
typedef struct TreeNode
{
    ElemType data;          // 节点数据
    struct TreeNode *lchid; // 左孩子指针
    struct TreeNode *rchid; // 右孩子指针
} TreeNode;

// 二叉树根节点指针的别名
typedef TreeNode* BinTree;

// 队列存储的元素类型：二叉树节点指针
typedef TreeNode* ElementType; 
#define MAX_SIZE 100 // 队列最大容量

// 队列结构体
typedef struct Queue{
    ElementType* data; // 存储 TreeNode* 的数组（本质是 TreeNode** 类型）
    int front;         // 队头指针
    int rear;          // 队尾指针
} Queue;

// 初始化队列
Queue* InitQueue(){
    Queue* q = (Queue*)malloc(sizeof(Queue));
    // 分配 MAX_SIZE 个 TreeNode* 的空间
    q->data = (ElementType*)malloc(MAX_SIZE * sizeof(ElementType));
    q->front = 0;
    q->rear = 0;
    return q;
}

char str[] = "ABDH#K###E##CFI###G#J##"; 
int idx = 0;  // 全局索引，标记字符串处理位置

// 前序遍历创建二叉树
void createTree(BinTree *t){
    ElemType ch = str[idx++]; // 取当前字符，索引后移

    if (ch == '#'){ // '#' 表示空节点
        *t = NULL;
    } else {
        *t = (BinTree)malloc(sizeof(TreeNode)); // 分配节点内存
        (*t)->data = ch;         // 设置节点数据
        createTree(&(*t)->lchid); // 递归创建左子树
        createTree(&(*t)->rchid); // 递归创建右子树
    } 
}

// 判断队列是否为空（1：空；0：非空）
int IsEmpty(Queue* q) { 
    return q->front == q->rear;
}

// 入队操作
int equeue(Queue* q, ElementType e){
    // 循环队列判满：(队尾+1) % 容量 == 队头
    if ((q->rear + 1) % MAX_SIZE == q->front){ 
        printf("队列已满。\n");
        return 0;
    }
    q->data[q->rear] = e;
    printf("入队节点：%c\n", e->data); // 打印节点字符
    q->rear = (q->rear + 1) % MAX_SIZE; 
    return 1;
}

// 出队操作
int dequeue(Queue *q, ElementType *e){
    if (q->front == q->rear) { // 队空判断
        printf("队列空！\n");
        return 0;
    }
    *e = q->data[q->front];
    printf("出队节点：%c\n", (*e)->data); // 打印节点字符
    q->front = (q->front + 1) % MAX_SIZE;
    return 1;
}

// 计算队列元素个数（循环队列正确计算方式）
int queueSize(Queue *Q){
    if (!IsEmpty(Q)){
        return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
    } else {
        return 0;
    }
}

// 层序遍历求二叉树最大深度
int maxDepth(TreeNode *root){
    if (root == NULL){
        return 0;
    }
    int depth = 0;
    Queue *q = InitQueue();
    equeue(q, root); // 根节点入队

    while (!IsEmpty(q)){
        int count = queueSize(q); // 当前层节点数
        while (count > 0){
            TreeNode *curr;
            dequeue(q, &curr); // 出队当前节点
            // 左右孩子非空则入队
            if (curr->lchid != NULL){
                equeue(q, curr->lchid);
            }
            if (curr->rchid != NULL){
                equeue(q, curr->rchid);
            }
            count--;
        }
        depth++; // 每处理完一层，深度+1
    }
    return depth;
}

int main(){
    BinTree T;
    createTree(&T); // 创建二叉树
    printf("二叉树的最大深度：%d\n", maxDepth(T));
    return 0;
}